package 数据结构练习;

//克鲁斯卡尔算法求最小生成树
public class 克鲁斯卡尔算法 {
    public static void main(String[] args) {
        int[][] map = new int[][]{
                {0,1,6},{0,3,5},
                {1,2,5},{2,3,7},
                {0,2,1},{1,4,3},
                {3,5,2},{2,4,5},
                {2,5,4},{4,5,6}
        };
        //冒泡排序排 b 数组
        int c[] = new int[3];
        for(int j=0;j<map.length-1;j++){
            for(int k=j;k<map.length;k++){
                if(map[j][2] > map[k][2]){
                    c = map[j];
                    map[j] = map[k];
                    map[k] = c;
                }
            }
        }
        kruskal(map);
    }

    public static void kruskal(int[][] map){
        //构建next数组，并初始化
        int[] next = new int[map.length];
        for(int x:next){
            x = -1;
        }
        //开始求最小生成树
        for(int[] x:map){
            //找到前一个点的终点
            while (next[x[0]] > 0){
                x[0] = next[x[0]];
            }
            //找到后一个点的终点
            while (next[x[1]] > 0){
                x[1] = next[x[1]];
            }
            //生成结点并打印
            if(x[0] != x[1]){
                next[x[0]] = x[1];
                System.out.println(x[0]+"->"+x[1]+" : "+x[2]);
            }
        }
    }
}
